#include <iostream>
#include <stack>
/*学习二叉树的基本知识，分别使用递归和循环的方式实现二叉树的先序创建和先序遍历*/
using namespace std;
//二叉树节点
struct Node
{
    char element;
    Node *leftchild;
    Node *rightchild;
    Node(){leftchild=rightchild=NULL;}
    Node(char theElement,Node *le=NULL,Node *ri=NULL)
    {
        element=theElement;
        leftchild=le;
        rightchild=ri;
    }
};
class Tree
{
public:
    Node *root;
    char voidone;//用来判断是否是空点
public:
     //用最不常用的‘#’来约定二叉树节点为空
    Tree(){
        root=NULL;
        voidone='#';
    }
     //先序遍历(递归方法)创造数组
    void Preordercreat(Node* &subTree)
    {
        char data;
        cin>>data;
        if (data != voidone)
        {
            subTree=new Node(data);
            Preordercreat(subTree->leftchild);
            Preordercreat(subTree->rightchild);
        }
        else
        {
            subTree=NULL;
        }
    }
    //使用栈的先序遍历，避免递归
    void Preview(Node* p)
    {
        stack<Node*> queue;
        queue.push(NULL);    //先加一个NULL来判断是否是最后一个节点没有左右孩子，这时就会结束循环
        while (p!=NULL)
        {
              cout << p->element ;
              if(p->rightchild!=NULL)
            //将右孩子指针放在在栈中
             {
                 queue.push(p->rightchild);
             }

             if (p->leftchild!=NULL)
             {
                 p = p->leftchild;
             }
             else //当这层左孩子为空后，开始遍历这层的右孩子
             {
                 p = queue.top();
                 queue.pop();
             }
        }
    }
};
int main()
{
    Tree t1;
    t1.Preordercreat(t1.root);
    //cout<<t1.root<<endl;
    t1.Preview(t1.root);
    return 0;
}
